import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/10 10:34
 * @description 可以枚举每个主件的所有选择方案，从而将问题转化为普通的「分组背包」问题
 * 利用每个主件最多只有  个附件，我们可以枚举每个主件的选择方案：只选主件、选主件和一个附件、选主件和两个附件。
 * 如此一来，我们将问题彻底转化为「分组背包」问题：
 * 组内最多选择一件物品；
 * 当前组不选任何物品，对应原问题中不选该主件及其附件的情况；
 * 当前组选任意一件物品，对应原问题中选择主件以及选择/不选某些附件的情况。
 */
public class Solution {
    public static void main(String[] args) {

    }
    /**
     * v[i]、p[i] 和 q[i] 分别代表第 i 件物品的价格、重要度、所依赖的主件（物品编号从 1 开始）
     */
    int[] v, p, q;
    /**
     * 金额、物品数
     */
    int n, m;

    public int maxValue(int _N, int _M, int[] _v, int[] _p, int[] _q) {
        n = _N; m = _M;
        v = _v; p = _p; q = _q;

        // 预处理出主件和附件的关系
        // { 主件1 : [附件1, 附件2], 主件2 : [], 主件3 : [附件1] ... }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 1; i <= m; i++) {
            if (q[i] == 0) {
                if (!map.containsKey(i)) map.put(i, new ArrayList<>());
            } else {
                List<Integer> list = map.getOrDefault(q[i], new ArrayList<>());
                list.add(i);
                map.put(q[i], list);
            }
        }

        // 构建物品组：list 装的每个物品组
        // [ [只选主件1, 选主件1和一个附件，选主件1和两个附件], [[主件2]], [[主件3, 主件3和附件1]] ... ]
        List<List<int[]>> list = new ArrayList<>();
        for (int root : map.keySet()) {
            List<int[]> group = new ArrayList<>();
            int rootv = v[root], rootw = v[root] * p[root];
            // 不选任何附件
            group.add(new int[]{rootv, rootw});

            List<Integer> sub = map.get(root);
            int cnt = sub.size();
            for (int i = 0; i < cnt; i++) {
                int x = sub.get(i);
                int xv = v[x], xw = v[x] * p[x];
                // 选一件附件
                group.add(new int[]{rootv + xv, rootw + xw});
                for (int j = i + 1; j < cnt; j++) {
                    int y = sub.get(j);
                    int yv = v[y], yw = v[y] * p[y];
                    // 选两件附件
                    group.add(new int[]{rootv + xv + yv, rootw + xw + yw});
                }
            }

            list.add(group);
        }

        // 分组背包一维空间优化：定义 f[i][j] 为考虑前 i 件物品，使用容量不超过 j 的最大价值
        int[] f = new int[n + 1];
        // 枚举物品组
        for (int i = 0; i < list.size(); i++) {
            List<int[]> group = list.get(i);
            // 枚举背包容量
            for (int j = n; j >= 0; j--) {
                // 枚举决策（选哪个组内物品）
                for (int k = 0; k < group.size(); k++) {
                    int[] info = group.get(k);
                    int vi = info[0], wi = info[1];
                    if (j >= vi) f[j] = Math.max(f[j], f[j - vi] + wi);
                }
            }
        }

        return f[n];
    }
}
